//
// Description: 3. 无重复字符的最长子串
// Created by Loading on 2021/8/11.
//

#include <bits/stdc++.h>

using namespace std;

int lengthOfLongestSubstring(string s) {
    // 存储字符和下标
    unordered_map<char, int> m;
    int res = 0;
    // 不重复子串开始位置
    int start = 0;
    for (int i = 0; i < s.size(); ++i) {
        if (m.count(s[i])) {
            // 更新开始位置
            /* 注意要和当前的 start 取 max */
            start = max(m[s[i]] + 1, start);
        }
        // 更新不重复子串最大长度
        res = max(res, i - start + 1);
        // 更新字符下标
        m[s[i]] = i;
    }
    return res;

    // 使用 hashset，无效运算较多
//    unordered_set<char> s_set;
//    int res = 0;
//    int right = 0;
//    for (int i = 0; i < s.size(); ++i) {
//        if (i != 0) {
//            s_set.erase(s[i - 1]);
//        }
//        while (right < s.size() && !s_set.count(s[right])) {
//            s_set.insert(s[right++]);
//        }
//        res = max(res, right - i);
//    }
//
//    return res;
}

int main() {
    string s = "qwroiuiqousjkfjkslf";
    int res = lengthOfLongestSubstring(s);
    cout << res << endl;
}